import java.util.Arrays;


public class StringManipulation {
	
	public static boolean isUniqueChars(String str){
		if(str.length() > 256){
			return false;
		}
		
		boolean[] char_index = new boolean[256];
		for(int i = 0; i < str.length(); i++){
			int p = str.charAt(i);
			if(char_index[p]){
				return false;
			}
			else{
				char_index[p] = true;
			}
		}
		
		return true;
	}

	public static String compress(String str){
		if (str == "" || str == null){
			return "";
		}
		if(str.length() == 1){
			return str;
		}
		
		char temp = str.charAt(0);
		int[] char_index = new int[256];
		StringBuffer sb = new StringBuffer();
		for(int i = 0; i < str.length(); i++){
			if(temp == str.charAt(i)){
				char_index[temp]++;
			}
			else{
				sb.append(str.charAt(i-1));
				sb.append(char_index[temp]);
				temp = str.charAt(i);
				char_index[str.charAt(i-1)] = 0;//previous char count clears to 0
				char_index[temp]++;
			}
			// last char in string
			if(i == str.length() -1 && str.charAt(i) == str.charAt(i-1)){
				sb.append(str.charAt(i));
				sb.append(char_index[str.charAt(i)]);
			}
			else if( i == str.length() -1 ){
				sb.append(str.charAt(i));
				char_index[str.charAt(i)]=1;
				sb.append(char_index[str.charAt(i)]);
			}
		}
		
		String result = sb.toString();;
		return result;
	}
	
	public String findLongestRepeatString(String str){
		if(str == null || str == ""){
			return "";
		}
		
		int N = str.length();
		
		String[] subStrings = new String[N];
		//seperate string to small piece from the end to start
		for(int i = 0; i < str.length(); i++){
			subStrings[i] = str.substring(i);
		}
		
		Arrays.sort(subStrings);
		String longestSubString = "";
		for(int j = 0; j < subStrings.length - 1; j++){
			String temp = stringCompare(subStrings[j], subStrings[j+1]);
			if(temp.length() > longestSubString.length()){
				longestSubString = temp;
			}
		}
		
		System.out.println(longestSubString);
		return longestSubString;
	}
	
	public String stringCompare(String str1, String str2){
		int length = Math.min(str1.length(), str2.length());
		System.out.println(str1 + ", " + str2);
		for(int i = 0; i < length; i++){
			if(str1.charAt(i) != str2.charAt(i)){
				return str1.substring(0, i);
			}
		}
		return str1.substring(0, length);
	}
	
	
	public String replaceSpaces(String str){
		if(str.length() == 0 || str == null){
			return null;
		}
		
		int spaceCount = 0;
		for(int i = 0; i < str.length(); i++){
			if(str.charAt(i) == ' '){
				spaceCount++;
			}
		}
		
		char[] char_arr = new  char[str.length() + spaceCount * 2];
		int index = str.length() + spaceCount * 2 - 1;
		
		for(int j = str.length() - 1; j >= 0; j--){
			if(str.charAt(j) != ' '){
				char_arr[index] = str.charAt(j);
				index--;
			}
			else{
				char_arr[index] = '0';
				char_arr[index - 1] = '2';
				char_arr[index - 2] = '%';
				index = index - 3;
			}
			
		}
		
		String result = char_arr.toString();
		System.out.println(char_arr);
		return result;
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(StringManipulation.compress("abcdef"));
		StringManipulation sm = new StringManipulation();
		sm.findLongestRepeatString("abcabcde");
		System.out.println(sm.isUniqueChars("a+-"));
		sm.replaceSpaces("Mr John Smith");
	}

}
